package class16;

import java.util.*;

/**
 * @author YZY
 * @since 2022/8/15 19:15
 */
public class Code03_TopologySort {

    // 拓扑排序
    public static List<MyGraph.Node<Integer>> topologySort(MyGraph.Graph<Integer> graph) {
        // 哈希表存储所有入度结点，Key结点，value入度数量
        Map<MyGraph.Node<Integer>, Integer> inMap = new HashMap<>();
        // 队列记录入度为0的结点
        Queue<MyGraph.Node<Integer>> zeroQueue = new ArrayDeque<>();
        // 将所有结点放入map中，放入过程中，遇到入度为0的放入queue中
        for (MyGraph.Node<Integer> node : graph.nodes.values()) {
            inMap.put(node, node.in);
            if (node.in == 0) {
                zeroQueue.add(node);
            }
        }
        // 拓扑排序结果
        List<MyGraph.Node<Integer>> result = new ArrayList<>();
        // 开始深度优先搜索
        while (!zeroQueue.isEmpty()) {
            MyGraph.Node<Integer> cur = zeroQueue.poll();
            result.add(cur);
            for (MyGraph.Node<Integer> no : cur.nexts) {
                inMap.put(no, inMap.get(no) - 1);
                if (inMap.get(no) == 0) {
                    zeroQueue.add(no);
                }
            }
        }
        return result;
    }

}
